//无向图采用临界表结构存储，要按深度优先搜索统计连通子图的个数，并输出所有连通子图的生成树 c语言
#include <stdio.h>
#include <stdlib.h>

// 边结构体，用于邻接表
typedef struct Edge {
    int to;
    struct Edge* next;
} Edge;

// 图结构体，包含邻接表头指针数组
typedef struct Graph {
    Edge** adjList;
    int V;  // 顶点个数
} Graph;

// 创建图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->adjList = (Edge**)malloc(V * sizeof(Edge*));
    for (int i = 0; i < V; i++) {
        graph->adjList[i] = NULL;
    }
    return graph;
}

// 添加边到图中
void addEdge(Graph* graph, int from, int to) {
    // 头插法添加边
    Edge* newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->to = to;
    newEdge->next = graph->adjList[from];
    graph->adjList[from] = newEdge;

    // 因为是无向图，所以反向边也要添加
    newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->to = from;
    newEdge->next = graph->adjList[to];
    graph->adjList[to] = newEdge;
}

// 释放图的内存空间
void freeGraph(Graph* graph) {
    for (int i = 0; i < graph->V; i++) {
        Edge* cur = graph->adjList[i];
        while (cur!= NULL) {
            Edge* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    free(graph->adjList);
    free(graph);
}

// 深度优先搜索标记数组，用于记录节点是否被访问过
int visited[100];

// 深度优先搜索函数，用于遍历一个连通子图，同时构建生成树
void DFS(Graph* graph, int v, int parent, FILE* outputFile) {
    visited[v] = 1;
    Edge* cur = graph->adjList[v];
    while (cur!= NULL) {
        int neighbor = cur->to;
        if (!visited[neighbor]) {
            // 将边加入生成树，输出到文件（这里以两个端点形式记录边）
            fprintf(outputFile, "(%d, %d)\n", v, neighbor);
            DFS(graph, neighbor, v, outputFile);
        }
        cur = cur->next;
    }
}

// 统计连通子图个数并输出所有连通子图的生成树，将生成树输出到文件
void countAndOutputConnectedComponents(Graph* graph) {
    int componentCount = 0;
    FILE* outputFile = fopen("output.txt", "w");
    if (outputFile == NULL) {
        printf("无法打开输出文件！\n");
        return;
    }
    for (int i = 0; i < graph->V; i++) {
        if (!visited[i]) {
            componentCount++;
            fprintf(outputFile, "连通子图 %d 的生成树的边为：\n", componentCount);
            DFS(graph, i, -1, outputFile);
            fprintf(outputFile, "\n");
        }
    }
    fclose(outputFile);
    printf("连通子图的个数为: %d\n", componentCount);
}

int main() {
    // 示例图，这里简单构造一个有5个顶点的图，可根据实际情况修改
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    for (int i = 0; i < 100; i++) {
        visited[i] = 0;
    }

    countAndOutputConnectedComponents(graph);
    freeGraph(graph);
    return 0;
}